#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : PalindromeLinkedList.py
# @Time    : 2020/10/23 15:22
# @Description: 
"""
- Linked List
- Two Pointers
- Stack
- Recursion
"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        """
        Given a singly linked list, determine if it is a palindrome.

        Example 1:
            Input: 1->2
            Output: false
        Example 2:
            Input: 1->2->2->1
            Output: true

        Follow up:
            Could you do it in O(n) time and O(1) space?

        :param head:
        :return:
        """
        if head is None or head.next is None:
            return True

        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)

        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next

        # restore the list and return the result
        first_half_end.next = self.reverse_list(second_half_start)
        return result

    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous

    def isPalindrome_v1(self, head: ListNode) -> bool:
        def find_last_node(head: ListNode):
            while head is not None and head.next is not None and head.next.next is not None:
                head = head.next
            return head
        num = 0
        cur_head = head
        while cur_head is not None:
            num += 1
            cur_head = cur_head.next
        
        for i in range(num//2):
            last_node = find_last_node(head)
            if head.val != last_node.next.val:
                return False
            last_node.next = None
            head = head.next
        return True
    
    def isPalindrome_v2(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return True
        x = []
        cur_head = head
        while cur_head:
            x.append(cur_head.val)
            cur_head = cur_head.next
        return x == x[::-1]


if __name__ == '__main__':
    x = [1, 2, 2, 1]
    head = None
    cur_head = None
    for i, v in enumerate(x):
        if i == 0:
            cur_head = ListNode(v)
            head = cur_head
        else:
            cur_head.next = ListNode(v)
            cur_head = cur_head.next

    S = Solution()
    # print(S.isPalindrome(head))
    # print(S.isPalindrome_v1(head))
    print(S.isPalindrome_v2(head))
    print('done')
